package com.rr.middle;

import java.util.Arrays;

/**
 * @author zhuangcanrun
 * @Date 2022/06/01/21:51
 * @description
 **/


/*
* https://leetcode.cn/problems/matchsticks-to-square/
* */
public class Makesquare {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        int length = matchsticks.length;
        for (int matchstick : matchsticks) {
            sum += matchstick;
        }
        if (sum % 4 != 0 || length < 4) {
            return false;
        }
        int targetLength = sum / 4;
        int[] array = new int[4];
        Arrays.sort(matchsticks);

        //从大到小排序，先放大边，减少递归次数
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }

        return dfs(0, matchsticks, array, targetLength);
    }

    private boolean dfs(int index, int[] matchsticks, int[] array, int targetLength) {
        if (index == matchsticks.length) {
            //进到这里说明所有火柴都已摆放完，即成功
            return true;
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = array[i] + matchsticks[index];
            //这根火柴放进去后还能把下一根放进去，就算成功
            if (array[i] <= targetLength && dfs(index + 1, matchsticks, array, targetLength)) {
                return true;
            }
            //回溯，这根放不进去这条边，换一条边放
            array[i] = array[i] - matchsticks[index];
        }
        //没有一条边放得进去，形成不了正方形
        return false;
    }

    public static void main(String[] args) {
        Makesquare makesquare = new Makesquare();
        System.out.println(makesquare.makesquare(new int[]{1,1,2,2,2}));
    }
}
